package com.kevinkk.tree;

import java.util.*;

/**
 * 迭代法 中序 遍历二叉树
 */

public class BinaryTreeInorderTraversal {
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            Deque<TreeNode> st = new LinkedList<>();    // ArrayDeque 不允许对 null 进行操作
            List<Integer> res = new ArrayList<>();
            if (root != null) st.addFirst(root);

            while (!st.isEmpty()) {
                TreeNode temp = st.peekFirst();

                if (temp == null) {
                    st.removeFirst();
                    res.add(st.removeFirst().val);
                } else {
                    st.removeFirst();   // 首先需要去除 null 节点
                    // 注意 栈的特点
                    if (temp.right != null) st.addFirst(temp.right);
                    st.addFirst(temp);
                    st.addFirst(null);
                    if (temp.left != null) st.addFirst(temp.left);
                }
            }
            return res;
        }
    }
}
